home *** CD-ROM | disk | FTP | other *** search
/ AOL File Library: 2,801 to 2,900 / aol-file-protocol-4400-2801-to-2900.zip / AOLDLs / C++ Files Library / Linked Lists Template Class 1.1 / Linked Lists 1.1 Ä.sit / Linked Lists 1.1 ƒ / source code / LinkedLists.cp < prev    next >
Text File  |  1995-03-15  |  8KB  |  332 lines
  1. #include "LinkedLists.h"
  2.  
  3. /***************************************************
  4.  
  5.     SlimListClass: Simple Pop and Push Features
  6.     
  7. ***************************************************/
  8.  
  9. template <class itemRecord> Boolean SlimListClass<itemRecord>::Push(itemRecord &theItem)
  10. {
  11.     ListItem<itemRecord> *newItem;
  12.     
  13.     newItem=new ListItem<itemRecord>;
  14.     newItem->item=theItem;
  15.     
  16.     if (newItem) {
  17.         newItem->next=stackTop;
  18.         stackTop=newItem;            //    stackTop variable always points to the top of the stack
  19.         return 1;
  20.     }
  21.     
  22.     return 0;
  23. }
  24.  
  25. template <class itemRecord> Boolean SlimListClass<itemRecord>::Pop(itemRecord &theItem)
  26. {
  27.     if (stackTop) {
  28.         theItem=stackTop->item;
  29.         ListItem<itemRecord> *temp=stackTop->next;
  30.         
  31.         delete stackTop;
  32.         stackTop=temp;
  33.         
  34.         return 1;
  35.     }
  36.     
  37.     return 0;
  38. }
  39.  
  40. template <class itemRecord> void SlimListClass<itemRecord>::DeleteAll()
  41. {
  42.     ListItem<itemRecord>    *temp=nil;
  43.     
  44.     if (stackTop) {
  45.         temp=stackTop->next;
  46.         delete stackTop;
  47.         stackTop=temp;
  48.     }
  49.     
  50.     while (temp) {
  51.         temp=stackTop->next;
  52.         delete stackTop;
  53.         stackTop=temp;
  54.     }
  55.         
  56. }
  57.  
  58. /****************************
  59. *                            *
  60. *    Stepping List            *
  61. *                            *
  62. ****************************/
  63.  
  64. template <class itemRecord> Boolean SteppingList<itemRecord>::Add(itemRecord &theItem)
  65. {
  66.     ListItem<itemRecord> *newItem, *tempItem;
  67.     
  68.     placeHolder=newItem=new ListItem<itemRecord>;
  69.     
  70.     if (newItem) {
  71.         numberOfItems++;
  72.         newItem->item=theItem;
  73.         
  74.         if (stackTop) {                            //    Go through whole list until end is found, add
  75.             tempItem=stackTop;                    //    newItem to the end
  76.             while (tempItem->next)
  77.                 tempItem=tempItem->next;
  78.             
  79.             tempItem->next=newItem;
  80.         }
  81.         
  82.         else
  83.             stackTop=newItem;
  84.             
  85.         newItem->next=nil;                        //    Set newItem->next to nil, connotating end of list
  86.         return 1;
  87.     }
  88.     
  89.     return 0;
  90. }    
  91.  
  92. template <class itemRecord> Boolean SteppingList<itemRecord>::Push(itemRecord &theItem)
  93. {
  94.     ListItem<itemRecord> *newItem;
  95.     
  96.     placeHolder=newItem=new ListItem<itemRecord>;
  97.     
  98.     if (newItem) {                        //    Essentially, this is the same as SlimSteppingListes,
  99.         numberOfItems++;                //    except that it updates the placeHolder var and the
  100.         newItem->item=theItem;            //    numberOfItems var
  101.         newItem->next=stackTop;
  102.         stackTop=newItem;
  103.         return 1;
  104.     }
  105.     
  106.     return 0;
  107. }
  108.  
  109. template <class itemRecord> Boolean SteppingList<itemRecord>::Pop(itemRecord &theItem)
  110. {
  111.     ListItem<itemRecord> *temp=stackTop;
  112.     
  113.     if (stackTop) {
  114.         theItem=stackTop->item;
  115.         placeHolder=stackTop=stackTop->next;
  116.         delete temp;
  117.         numberOfItems--;
  118.         return 1;
  119.     }
  120.     return 0;
  121. }
  122.  
  123. template <class itemRecord> void SteppingList<itemRecord>::Delete(itemRecord theItem)
  124. {
  125.     ListItem<itemRecord>    *tempItem=stackTop;
  126.     
  127.     if (tempItem->item==theItem) {
  128.         placeHolder=stackTop=stackTop->next;
  129.         delete tempItem;
  130.         numberOfItems--;
  131.     }
  132.     
  133.     else {
  134.     
  135.         while (tempItem->next->item!=theItem && tempItem)
  136.             tempItem=tempItem->next;
  137.             
  138.         if (tempItem) {
  139.             ListItem<itemRecord>    *oldItem=tempItem->next;
  140.             
  141.             placeHolder=tempItem->next=tempItem->next->next;
  142.             delete oldItem;
  143.             numberOfItems--;
  144.         }
  145.     }
  146.     
  147. }
  148.         
  149. template <class itemRecord> void SteppingList<itemRecord>::DeleteAll()
  150. {
  151.     ListItem<itemRecord>    *temp=stackTop;
  152.     
  153.     while (temp) {                    //    Essentially the same as the SlimSteppingList DeleteAll
  154.         temp=stackTop->next;
  155.         delete stackTop;
  156.         stackTop=temp;
  157.     }
  158.     numberOfItems=0;
  159.     placeHolder=stackTop;
  160. }
  161.  
  162. template <class itemRecord> ListItem<itemRecord> * SteppingList<itemRecord>::GetTopItem(itemRecord * &theItem)
  163. {
  164.     if (SetToTop())
  165.         theItem=&(placeHolder->item);
  166.     return placeHolder;
  167. }
  168.  
  169. template <class itemRecord> ListItem<itemRecord> * SteppingList<itemRecord>::GetPlaceItem(itemRecord * &theItem)
  170. {
  171.     if (placeHolder)
  172.         theItem=&(placeHolder->item);
  173.     return placeHolder;
  174. }
  175.  
  176. template <class itemRecord> ListItem<itemRecord> * SteppingList<itemRecord>::GetNextItem(itemRecord * &theItem)
  177. {
  178.     if (placeHolder)                    //    Check to make sure placeHolder is valid address
  179.         placeHolder=placeHolder->next; 
  180.     if (placeHolder)                     //    Check to make sure it still is, after pointing to the next
  181.         theItem=&(placeHolder->item);     //    If everything checks out, set second parameter to address
  182.     return placeHolder;                    //    of placeHolder's item
  183. }
  184.  
  185. template <class itemRecord> ListItem<itemRecord> * SteppingList<itemRecord>::GetBottomItem(itemRecord * &theItem)
  186. {
  187.     if (placeHolder)                            //    Start where we are, if we can, instead
  188.         while (placeHolder->next)                //    of simply going to the stack top
  189.             placeHolder=placeHolder->next;
  190.     else if ((placeHolder=stackTop)!=nil)        //    Otherwise, go to the stack top and go down list
  191.         while (placeHolder->next)
  192.             placeHolder=placeHolder->next;
  193.     if (placeHolder)
  194.         theItem=&(placeHolder->item);
  195.     
  196.     return placeHolder;
  197. }
  198.  
  199. template <class itemRecord> ListItem<itemRecord> * SteppingList<itemRecord>::GetItemX(short itemNumber, itemRecord * &theItem)
  200. {
  201.     short n=1;
  202.  
  203.     if (itemNumber>numberOfItems)
  204.         return nil;
  205.     
  206.     SetToTop();
  207.     while (n++!=itemNumber)
  208.         placeHolder=placeHolder->next;
  209.     
  210.     theItem=&(placeHolder->item);
  211.     
  212.     return placeHolder;
  213. }
  214.  
  215. template <class itemRecord> ListItem<itemRecord> * SteppingList<itemRecord>::ItemInList(itemRecord *theItem)
  216. {
  217.     itemRecord    *tempItem;
  218.     if (placeHolder)
  219.         if (placeHolder->item==*theItem)
  220.             return placeHolder;
  221.     if (GetTopItem(tempItem)) {
  222.         if (*tempItem==*theItem)
  223.             return placeHolder;
  224.         else
  225.             while (GetNextItem(tempItem))
  226.                 if (*tempItem==*theItem)
  227.                     return placeHolder;
  228.     }
  229.     return nil;
  230. }
  231.  
  232. template <class itemRecord> ListItem<itemRecord> * SteppingList<itemRecord>::Cycle(itemRecord *currentItem, itemRecord * &nextItem)
  233. {
  234.     ListItem<itemRecord> * temp=ItemInList(currentItem);    //    this will find the item in the list
  235.                                                             //    and return a pointer to it.  More
  236.                                                             //    importantly, it will set the 
  237.                                                             //    placeHolder to the position, so we
  238.                                                             //    know to look for the next item
  239.     
  240.     if (temp) {
  241.         if (placeHolder->next)
  242.             placeHolder=placeHolder->next;
  243.         else
  244.             placeHolder=stackTop;
  245.         nextItem=&(placeHolder->item);
  246.     }
  247.     
  248.     return temp;
  249. }
  250.  
  251. template <class itemRecord> int SteppingList<itemRecord>::NumItems()
  252. {
  253.     return numberOfItems;
  254. }
  255.  
  256. /****************************************************
  257. *                                                    *
  258. *    ComparisonList:                                 *
  259. *                                                    *
  260. ****************************************************/
  261.  
  262. template <class itemRecord, class comparisonObject> Boolean ComparisonList<itemRecord, comparisonObject>::XInList(comparisonObject theObject, itemRecord * &theItem)
  263. {
  264.     ListItem<itemRecord>    *top;
  265.     
  266.     placeHolder=stackTop;
  267.     
  268.     if (stackTop) {
  269.         if (stackTop->item==theObject) {
  270.             theItem=&(stackTop->item);                //    Set theItem to the address of the item's address
  271.             return 1;
  272.         }
  273.         else 
  274.             while ((placeHolder=placeHolder->next)!=nil) {
  275.                 if (placeHolder->item==theObject) {
  276.                     theItem=&(placeHolder->item);    //    Set theItem to the address of the item's address
  277.                     return 1;
  278.                 }
  279.             }
  280.     }
  281.     
  282.     return 0;
  283. }
  284.  
  285.  
  286. /****************************************************
  287. *                                                    *
  288. *    SortingList:                                     *
  289. *                                                    *
  290. ****************************************************/
  291.  
  292. template <class itemRecord> Boolean SortingList<itemRecord>::AddSort(itemRecord &theItem)
  293. {
  294.     ListItem<itemRecord> *newItem, *tempItem;
  295.     
  296.     placeHolder=newItem=new ListItem<itemRecord>;
  297.     
  298.     if (newItem) {
  299.         numberOfItems++;
  300.         newItem->item=theItem;
  301.     
  302.         ListItem<itemRecord>    *tempItem;
  303.                 
  304.         if (stackTop) {                            //    If stackTop is not nil, a stack is present
  305.         
  306.             if (theItem<stackTop->item) {        //    Set newItem->next to stackTop if it's less and
  307.                 newItem->next=stackTop;            //    set stackTop to newItem 
  308.                 stackTop=newItem;
  309.             }
  310.             
  311.             else {
  312.                 tempItem=stackTop;                //     Otherwise, put insert it in first spot it's less
  313.                                                 //    than an other item
  314.                 while (theItem>tempItem->next->item && tempItem->next)
  315.                     tempItem=tempItem->next;
  316.                 
  317.                 newItem->next=tempItem->next;
  318.                 tempItem->next=newItem;
  319.             }
  320.         }
  321.         
  322.         else {                                    //    Stack is created, set stackTop to newItem
  323.             stackTop=newItem;
  324.             newItem->next=nil;
  325.         }
  326.     return (1);
  327.     }
  328.     
  329.     return (0);
  330. }
  331.  
  332.